Trapping Rain Water II || First Missing Positive

发表于

Trapping Rain Water II

Question

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

1
2
3
4
5
6
7
8
Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]
Return 4.

Analysis

LeetCode Discuss 利用Priority Queue解法

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Solution {
    public class Cell {
        private int row;
        private int col;
        private int height;
        private Cell(int row, int col, int height){
            this.row=row;
            this.col=col;
            this.height=height;
        }
    }
    
    public int trapRainWater(int[][] heightMap) {
        int m=heightMap.length;
        if(m<=2)  return 0;
        int n=heightMap[0].length;
        if(n<=2)  return 0;
        boolean[][] visited=new boolean[m][n];
        
        PriorityQueue<Cell> queue=new PriorityQueue<>(1,new Comparator<Cell>(){
            public int compare(Cell a, Cell b){
                return a.height-b.height;
            }
        });
        
        for(int i=0;i<m;i++){
            visited[i][0]=true;
            visited[i][n-1]=true;
            queue.offer(new Cell(i,0,heightMap[i][0]));
            queue.offer(new Cell(i,n-1,heightMap[i][n-1]));
        }
        
        for(int j=0;j<n;j++){
            visited[0][j]=true;
            visited[m-1][j]=true;
            queue.offer(new Cell(0,j,heightMap[0][j]));
            queue.offer(new Cell(m-1,j,heightMap[m-1][j]));
        }
        
        //Set Directions
        int water=0;
        while(!queue.isEmpty()){
            Cell tmp=queue.poll();
            for(int[] dir:direction){
                int row=tmp.row+dir[0];
                int col=tmp.col+dir[1];
                if(row>=0&&row<m&&col>=0&&col<n&&!visited[row][col]){
                    visited[row][col]=true;
                    water+=Math.max(0,tmp.height-heightMap[row][col]);
                    queue.offer(new Cell(row,col,Math.max(heightMap[row][col],tmp.height)));
                }
            }
        }
        
        return water;
    }
}

First Missing Positive

Question

Given an unsorted integer array, find the first missing positive integer.

For example,
Given[1,2,0] return 3,
and [3,4,-1,1] return2.

Analysis

LeetCode Discuss

从头到尾遍历，将每个大于0且小于等于长度len的数i都放在数组i-1的位置上，最后再从头遍历一次，找到第一个num[i]!=i+1的即所需结果

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int firstMissingPositive(int[] nums) {
        int len=nums.length;
        int tmp=0;
        for(int i=0;i<len;i++){
            while(nums[i]>0&&nums[i]<=len&&nums[nums[i]-1]!=nums[i]){    //Swap(A[A[i]-1],A[i])
                tmp=nums[i];
                nums[i]=nums[tmp-1];
                nums[tmp-1]=tmp;
            }
        }
        
        for(int i=0;i<len;i++){
            if(nums[i]!=i+1)
                return i+1;
        }
        return len+1;
    }
}